/**
 * 
 */
package cz.cuni.mff.abacs.burglar.visual.multithreading;

import cz.cuni.mff.abacs.burglar.logics.DataMap;
import cz.cuni.mff.abacs.burglar.logics.GameMap;
import cz.cuni.mff.abacs.burglar.logics.objects.agents.Agent;
import cz.cuni.mff.abacs.burglar.logics.objects.agents.Burglar;
import cz.cuni.mff.abacs.burglar.logics.objects.agents.Guard;
import cz.cuni.mff.abacs.burglar.logics.objects.positions.Door;
import cz.cuni.mff.abacs.burglar.logics.planning.PlannerHandler;
import cz.cuni.mff.abacs.burglar.logics.planning.PlannerHandlerFactory;
import cz.cuni.mff.abacs.burglar.logics.planning.instructions.Instruction;
import cz.cuni.mff.abacs.burglar.visual.VisualBurglar;
import cz.cuni.mff.abacs.tools.CombinationGenerator;
import java.util.*;


/**
 * Thread to execute the planning and forward the results to the planning listener.
 * 
 * @author abacs
 *
 */
public class PlanningThread extends Thread {
	
	
	// constants:
	
	/** Planning type. */
	public enum Type {
		PLANNING,
		PLANNING_BURGLAR,
		PLANNING_AGENTS,
		SELECTING_TRAP_ROOMS,
	}
	
	
	// -------------------------------------------------------------------------
	// properties:
	
	
	/** Address to return the results. */
	private final PlanningListener _listener;
	
	/** Object to execute the planning. */
	private final PlannerHandler _planner = 
		PlannerHandlerFactory.createPlannerHandler();
	
	/** Map to execute the planning on. */
	private final GameMap _map;
	
	/** List of agents to plan for. */
	private List<Agent> _agents = null;
	
	/** Planning type. */
	private final Type _type;
	
	
	// -------------------------------------------------------------------------
	// constructors:
	
	
	/**
	 * Simple constructor.
	 * 
	 * @param map map subject to plan on.
	 * @param type planning type
	 * @param listener address for the results
	 */
	public PlanningThread(
			GameMap map,
			Type type,
			PlanningListener listener
	) {
		super();
		this._map = map;
		this._type = type;
		this._listener = listener;
	}
	
	
	/**
	 * Constructor to plan for selected agents.
	 * 
	 * @param map map subject to plan on.
	 * @param listener address for the results
	 * @param agentsToPlan agents that need planning
	 */
	public PlanningThread(
			GameMap map,
			PlanningListener listener,
			List<Agent> agentsToPlan
	) {
		super();
		this._map = map;
		this._type = Type.PLANNING_AGENTS;
		this._listener = listener;
		this._agents = agentsToPlan;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	/* (non-Javadoc)
	 * @see java.lang.Runnable#run()
	 */
	@Override
	public void run() {
		long startTime = System.currentTimeMillis();
		
		switch(this._type){
		case PLANNING:
			// the order of the following two instructions is important!
			// planBurglar does removes the planning flag
			this.planGuards();
			this.planBurglar();
			break;
		case PLANNING_BURGLAR:
			this.planBurglar();
			break;
		case SELECTING_TRAP_ROOMS:
			this.selectTrapRooms();
			break;
		case PLANNING_AGENTS:
			for(Agent agent : this._agents){
				
				// only active agents should plan:
				if(agent.isInState(Agent.State.WELL) == false)
					continue;
				
				this.planAgent(agent);
			}
			this._listener.planningFinished(this);
			break;
		}
		
		// print out the planning duration:
		long endTime = System.currentTimeMillis();
		long duration = endTime - startTime;
		
		System.out.println(
				"- Planning time: " + duration + " ms. (" + this._type + ')'
		);
		
	}
	
	
	// -------------------------------------------------------------------------
	
	
	
	
	// -------------------------------------------------------------------------
	
	
	private void planBurglar() {
		List<Integer> emptyList = new LinkedList<Integer>();
		List<Integer> avoidedTrapRooms = new ArrayList<Integer>();
		
		// instructions that the burglar would normally follow:
		List<Instruction> freeInstructions = 
			this._planner.solveBurglarProblem(
					this._map,
					emptyList,
					emptyList
			);
		
		// for each trap in the map control whether the avoiding plan matches 
		// the burglar's normal plan
/*		for(Integer trapRoomId : this._map.getTrapRoomIds()){
			
			List<Integer> trapRooms = new LinkedList<Integer>();
			trapRooms.add(trapRoomId);
			
			List<Instruction> avoidInstructions = 
				this._planner.solveBurglarProblem(
						this._map,
						emptyList,
						trapRooms
				);
			
			if(this._map.instructionListsMatch(freeInstructions, avoidInstructions)){
				System.out.println("- trap room " + trapRoomId + " avoided");
				avoidedTrapRooms.add(trapRoomId);
			}
			
		}	*/
		
		this._listener.planningFinished(freeInstructions, avoidedTrapRooms, this);
	}
	
	
	/**
	 * 
	 */
	private void planGuards() {
		List<Instruction> result = new LinkedList<Instruction>();
		List<Integer> emptyList = new LinkedList<Integer>();
		
		for(Guard guard : this._map.getGuards()){
			
			// instructions that the burglar would normally follow:
			List<Instruction> instructions = 
				this._planner.solveGuardProblem(
						guard,
						this._map,
						guard.getRoomsToVisit(),
						emptyList
				);
			result.addAll(instructions);
		}
		
		this._listener.planningFinished(result, this);
	}
	
	
	/**
	 * 
	 * @param agent 
	 */
	private void planAgent(Agent agent) {
		List<Integer> emptyList = new LinkedList<Integer>();
		List<Instruction> result;
		
		switch(agent.getType()){
		case BURGLAR:
			
			result = this._planner.solveBurglarProblem(
					this._map,
					emptyList,
					emptyList
			);
			
			this._listener.planningFinished(result, this);
			break;
			
		case GUARD:
			
			Guard guard = (Guard)agent;
			result = this._planner.solveGuardProblem(
					guard,
					this._map,
					emptyList,
					emptyList
			);
			
			this._listener.planningFinished(result, this);
			break;
			
		default:
			
		}
	}
	
	
	private void selectTrapRooms() {
		if(VisualBurglar.FLAG_INVALIDATE_PREVIOUS_PATH){
			selectTrapRoomsWithPathInvalidating();
		}else{
			selectTrapRoomsWithoutPathInvalidating();
		}
	}
	
	
	private void selectTrapRoomsWithoutPathInvalidating() {
		// 
		// plan a burglar path to get the rooms it uses:
		// 
		
		List<Integer> emptyList = new LinkedList<Integer>();
		
		// instructions that the burglar would normally follow:
		List<Instruction> originalPlan = 
			this._planner.solveBurglarProblem(this._map, emptyList, emptyList);
		List<Integer> originalRooms = 
			getPlannedRoomIds(originalPlan, (DataMap)this._map);
		
		List<Integer> filteredRooms = this.removeUnavoidableRooms(originalRooms);
		
		// TODO
		debugPrint(
				"original path rooms (" + filteredRooms.size() + "): ",
				filteredRooms, ""
		);
		
		//
		// insert trap rooms:
		//
		
		int trapRoomCount = this._map.getRequiredTrapRoomCount();
		if(trapRoomCount > filteredRooms.size())
			trapRoomCount = filteredRooms.size();
		
		List<Integer> trapRooms = new ArrayList<Integer>(trapRoomCount);
		
		// try the maximal number of trap rooms the user wants, if not possible
		// try less:
		trapRoomCount++;
		while(trapRooms.isEmpty() && --trapRoomCount > 0){
			
			PseudoRandomCombinationGenerator gener = 
					new PseudoRandomCombinationGenerator(
							filteredRooms.size(),
							trapRoomCount
					);
			
			// try all combinations of trap rooms for the current trap room count
			while(gener.hasMore()){
				// generate a trap room configuration:
				int[] combination = gener.getNext();
				
				selectSublist(filteredRooms, combination, trapRooms);
				
				// test the trap room configuration:
				List<Instruction> restrictedPlan = 
					this._planner.solveBurglarProblem(this._map, emptyList, trapRooms);
				
				// TODO
				debugPrint(
						"trap rooms (" + trapRoomCount + ") tried: ",
						trapRooms,
						"does it work: " + !restrictedPlan.isEmpty()
				);
				
				// exit if plan is valid:
				if(restrictedPlan.isEmpty())
					trapRooms.clear();
				else
					break;
			}
		}
		
		//
		// insert traps to trap rooms
		//
		
		// TODO
		debugPrint("trap rooms that worked out ("+trapRoomCount+"): ", trapRooms, "");
		
		this._listener.selectingTrapRoomsFinished(trapRooms, this);
	}
	
	
	/**
	 * 
	 */
	private void selectTrapRoomsWithPathInvalidating() {
		// 
		// plan a burglar path to get the rooms it uses:
		// 
		
		List<Integer> emptyList = new LinkedList<Integer>();
		
		List<Integer> avoidableRooms = new ArrayList<Integer>(this._map.getRoomIds().size());
		List<Integer> unavoidableRooms = new ArrayList<Integer>(this._map.getRoomIds().size());
		
		// get the unavoidable rooms:
		List<Integer> roomsToAvoid = new ArrayList<Integer>(1);
		for(Integer roomToTest : this._map.getRoomIds()){
			
			roomsToAvoid.clear();
			roomsToAvoid.add(roomToTest);
			
			// instructions that the burglar would follow without roomToTest:
			List<Instruction> plan = 
				this._planner.solveBurglarProblem(this._map, emptyList, roomsToAvoid);
			
			// if there is a way, it's avoidable
			if(plan.isEmpty() == false){
				avoidableRooms.add(roomToTest);
				// debug print:
				System.out.println("room avoidable:" + roomToTest);
			}else{
				unavoidableRooms.add(roomToTest);
				// debug print:
				System.out.println("room unavoidable:" + roomToTest);
			}
		}
		
		if(avoidableRooms.isEmpty())
			return;
		
		int maxTraps = this._map.getRequiredTrapRoomCount();
		if(maxTraps > avoidableRooms.size())
			maxTraps = avoidableRooms.size();
		
		// plan the traprooms:
		roomsToAvoid.clear();
		List<Integer> trapRooms = new ArrayList<Integer>(maxTraps);
		List<Integer> finalPathRooms = new LinkedList<Integer>();
		int roomIndex = 0;
		
		for(int trapCounter = 0; trapCounter < maxTraps; trapCounter++){
			
			// instructions that the burglar would follow:
			List<Instruction> plan = 
				this._planner.solveBurglarProblem(this._map, finalPathRooms, roomsToAvoid);
			List<Integer> pathRooms = getPlannedRoomIds(plan, (DataMap)this._map);
			
			// TODO test plan success
			
			// select the first available avoidable room in the path:
			// (index has to be larger than the last index)
			for(; roomIndex < pathRooms.size(); roomIndex++){
				
				int currentRoom = pathRooms.get(roomIndex);
				roomsToAvoid.add(currentRoom);
				List<Instruction> avoidingPlan = 
					this._planner.solveBurglarProblem(this._map, finalPathRooms, roomsToAvoid);
				roomsToAvoid.remove(roomsToAvoid.size() - 1);
					
				if(avoidingPlan.isEmpty()){
					finalPathRooms.add(pathRooms.get(roomIndex));
				}else{
					break;
				}
			}
			
			if(roomIndex >= pathRooms.size())
				break;
			
			// add room to traprooms:
			trapRooms.add(pathRooms.get(roomIndex));
			
			
			
			// set the rooms to avoid as avoidable rooms
			// on current path starting with the last traproom:
			roomsToAvoid.clear();
			for(int avoidIndex = roomIndex; avoidIndex < pathRooms.size(); avoidIndex++){
				roomsToAvoid.add(pathRooms.get(roomIndex));
			}
			roomsToAvoid.addAll(trapRooms);
			
		}
		
		// TODO
		debugPrint("secondary: trap rooms that worked out ("+trapRooms.size()+"): ", trapRooms, "");
		
		this._listener.selectingTrapRoomsFinished(trapRooms, this);
	}
	
	
	protected List<Integer> removeUnavoidableRooms(
		List<Integer> originalRooms	
	) {
		List<Integer> filteredRooms = new LinkedList<Integer>(originalRooms);
		
		// remove current room:
		Burglar burglar = this._map.getBurglar();
		if(filteredRooms.contains(burglar.getRoomId()))
			filteredRooms.remove(filteredRooms.indexOf(burglar.getRoomId()));
		
		// remove aim room:
		if(filteredRooms.contains(burglar.getAimId()))
			filteredRooms.remove(filteredRooms.indexOf(burglar.getAimId()));
		
		
		// remove the rooms that can't be walked around:
		List<Integer> trapRooms = new ArrayList<Integer>(1);
		List<Integer> roomsToControl = new ArrayList<Integer>(filteredRooms);
		List<Integer> emptyList = new LinkedList<Integer>();
		
		for(Integer roomId : roomsToControl){
			// test the trap room configuration:
			
			trapRooms.add(roomId);
			List<Instruction> restrictedPlan = 
				this._planner.solveBurglarProblem(this._map, emptyList, trapRooms);
			
			// TODO
			System.out.println(
					"is room required? id: " + 
					roomId + " " + restrictedPlan.isEmpty()
			);
			
			// exit if plan is not valid, current room is needed:
			if(restrictedPlan.isEmpty())
				filteredRooms.remove(filteredRooms.indexOf(roomId));
			
			trapRooms.clear();
		}
		
		return filteredRooms;
	}
	
	
	/**
	 * Returns the rooms that the agent plans to visit.
	 * 
	 * @param instructions
	 * @param referenceMap
	 * @return
	 */
	protected static List<Integer> getPlannedRoomIds(
			List<Instruction> instructions, 
			DataMap referenceMap
	) {
		Set<Integer> rooms = new HashSet<Integer>();
		
		for(Instruction instr : instructions){
			if(instr._code == Instruction.code.ENTER_DOOR){
				Door subject = (Door)referenceMap.getPosition(instr._subjectId);
				int[] doorRooms = subject.getRoomIds();
				rooms.add(doorRooms[0]);
				rooms.add(doorRooms[1]);
			}
		}
		
		List<Integer> result = new ArrayList<Integer>(rooms.size());
		for(Integer roomId : rooms)
			result.add(roomId);
		
		return result;
	}
	
	
	/** 
	 * Selects subelements and places them to destination list.
	 * 
	 * @param source source list
	 * @param indexes indexes to copy
	 * @param destination destination list
	 */
	private static void selectSublist(
			List<Integer> source,
			int[] indexes,
			List<Integer> destination
	) {
		destination.clear();
		for(int i = 0; i < indexes.length; i++)
			destination.add(source.get(indexes[i]));
	}
	
	
	// TODO debug
	/**
	 * 
	 * @param leadingText
	 * @param ids
	 * @param endingText
	 */
	private static void debugPrint(
			String leadingText,
			List<Integer> ids,
			String endingText
	) {
		System.out.print(leadingText);
		for(Integer id : ids)System.out.print(id + ", ");
		System.out.println(endingText);
	}
	
	
	// -------------------------------------------------------------------------
	
	
	private class PseudoRandomCombinationGenerator {
		// constants:
		
		
		/**  */
		private final int BUFFER_SIZE = 500;
		
		
		// ---------------------------------------------------------------------
		// properties:
		
		
		/**  */
		private final CombinationGenerator _gener;
		
		
		/**  */
		private final List<int[]> _buffer = new ArrayList<int[]>(BUFFER_SIZE);
		
		
		// ---------------------------------------------------------------------
		// constructors:
		
		
		/**
		 * 
		 * @param n
		 * @param r
		 */
		public PseudoRandomCombinationGenerator(int n, int r) {
			this._gener = new CombinationGenerator(n, r);
			this.fillBuffer();
		}
		
		
		// ---------------------------------------------------------------------
		
		
		/**
		 * 
		 * @return
		 */
		public boolean hasMore() {
			return this._buffer.isEmpty() == false || this._gener.hasMore();
		}
		
		
		/**
		 * 
		 * @return
		 */
		public int[] getNext() {
			if(this._buffer.isEmpty()){
				if(this._gener.hasMore()){
					this.fillBuffer();
					return this.getNext();
				}
				return null;
			}
			return this._buffer.remove(0);
		}
		
		
		// ---------------------------------------------------------------------
		
		
		/**
		 * 
		 */
		private void fillBuffer() {
			while(this._buffer.size() < BUFFER_SIZE && this._gener.hasMore())
				this._buffer.add(this._gener.getNext().clone());
			Collections.shuffle(this._buffer);
		}
		
		
	}
	
	
}
